//
// Created by LaiChao on 2021/6/10.
//
// AcWing上yxc的算法课代码
#include <vector>
#include <deque>
#include <string>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

const int N = 10e5;     // 默认大小，适当修改
const int HashN = 100003;
vector<int> tree(10e7);

//************************************************************************
//                              第一章: 基础算法
//************************************************************************
class TemplateAlgorithm {
public:
    static void quickSort(vector<int> &nums);           // 快速排序(nLogn)
    static void mergeSort(vector<int> &nums);           // 归并排序(nLogn)
    static void heapSort(vector<int> &nums);            // 堆排序(nLogn)
    static vector<int> singleStack(vector<int> &nums);      // 单调栈 —— 模板题 AcWing 830. 单调栈
    // static vector<int> maxSlidingWindow(vector<int> &nums); // 单调队列 —— 模板题 AcWing 154. 滑动窗口
    static int lengthOfLongestSubstring(string s);      // 双指针
    static int numOfOne(int x);     // 返回整数二进制形式中1的个数
    static vector<vector<int>> merge(vector<vector<int>> &intervals);       // 56. 合并区间

    // DFS Questions
    static vector<string> permutation(string s);        // 剑指 Offer 38. 字符串的排列(全排列模板)
    static vector<vector<string>> solveNQueens(int n);  // 51. N 皇后

    // BFS Questions
    // static bool isEscapePossible(vector<vector<int>> &blocked, vector<int> &source, vector<int> &target); // 1036. 逃离大迷宫
    static vector<int> topoSort();        // 拓扑排序
};

//************************************************************************
//                              第二章: 数据结构
//************************************************************************
// 1. 单链表(===> 邻接表:存储图和树) ===== AcWing 826.单链表
// 数组模拟链表（属于静态链表，传统方式（动态链表）new结点速度太慢）
class ListNodeClass {
public:
    void init() {   // 初始化链表
        head = -1;
        index = 0;
    }

    void add_to_head(int val) {   // 插入到头节点
        elements[index] = val;
        next[index] = head;
        head = index;
        index++;
    }

    void add(int val, int pos) {    // 插入节点：val插入到pos节点后
        elements[index] = val;
        next[index] = next[pos];
        next[pos] = index;
        index++;
    }

    void remove(int pos) {      // 删除节点下标为k的后一个节点
        next[pos] = next[next[pos]];  // 算法题中不考虑内存泄露问题
    }

private:
    int index;  // 表示当前用到了哪个节点
    int head;   // 表示头结点的下标
    int elements[N];   // 表示第i个节点的值
    int next[N];  // 表示第i个节点的next指针是多少
};

// 2. 双链表
// 数组模拟链表（属于静态链表，传统方式（动态链表）new结点速度太慢）
class BiListNodeClass {
public:
    void init() {   // 初始化链表
        // 0 表示左端点，1 表示右端点(偷懒做法)
        right[0] = 1, left[1] = 0;
        index = 2;
    }

    void add(int pos, int val) {    // 插入节点：val插入到pos节点的右边
        // 如果要实现在pos的左边插入val，只需要调用 add(left[pos], val) 即可
        ele[index] = val;
        left[index] = pos;  // 一共涉及四个指针操作
        right[index] = right[pos];
        left[right[pos]] = index;
        right[pos] = index;
    }

    void remove(int pos) {      // 删除pos节点
        right[left[pos]] = right[pos];
        left[right[pos]] = left[pos];
    }

private:
    int index;  // 表示当前用到了哪个节点
    int ele[N];   // 表示第i个节点的值
    int left[N], right[N];  // 表示第i个节点的next指针是多少
};

// 3. 栈
// 数组模拟栈
class StackClass {
public:
    void init() {   // 初始化栈
        pos = 0;
    }

    void add(int val) { // 添加元素
        stk[++pos] = val;
    }

    void remove() {     // 移除栈顶元素
        --pos;
    }

    bool isEmpty() {     // 判空
        return pos > 0;
    }

    int top() {     // 返回栈顶元素
        return stk[pos];
    }

private:
    int stk[N]; // 存放数据
    int pos;    // 栈顶元素坐标
};

// 4. 队列
// 数组模拟队列
class QueueClass {
public:
    void init() {   // 初始化队列
        tail = -1;
    }

    void add(int val) {     // 插入元素
        que[++tail] = val;
    }

    void remove() {     // 队首弹出元素
        if (!isEmpty()) ++head;
    }

    bool isEmpty() {    // 判空
        return head > tail;
    }

    int front() {       // 取出队头元素
        return que[head];
    }

private:
    int que[N];
    int head, tail;
};

// Trie：高效存储和查找字符串集合的数据结构(模板）
class TrieTree {
public:
    void insert(char str[]) {   // 存储，插入操作
        int p = 0;
        for (int i = 0; str[i]; i++) {  // 遍历字符串，str[i]以 '/0' 结尾，用来判断
            int u = str[i] - 'a';
            if (!son[p][u]) son[p][u] = ++index;    // 创建
            p = son[p][u];
        }
        cnt[p]++;
    }

    int query(char str[]) {     // 返回字符串出现次数
        int p = 0;
        for (int i = 0; str[i]; i++) {
            int u = str[i] - 'a';
            if (!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }

private:
    int son[N][26];     // 树中每个点的所有儿子，N可以理解为字符串的长度
    int cnt[N];         // 以当前点结尾的单词个数
    int index;  // 下标是0的点，既是根节点又是空节点
};

// 哈希结构——链表法
class LinkHash {
public:
    void insert(int x) {
        // 哈希映射函数获取哈希值
        int k = (x % HashN + HashN) % HashN;    // 加上HashN保证映射后的值为正数
        element[index] = x;     // 插入位置是链的最前端
        next[index] = HashVec[k];
        HashVec[k] = index++;
    }

    bool find(int x) {
        int k = (x % HashN + HashN) % HashN;
        // 沿着链表查找
        for (int i = HashVec[k]; i != -1; i = next[i]) {
            if (element[i] == x) return true;
        }
        return false;
    }

private:
    vector<int> HashVec;    // 开出的槽，用于存放映射后的值(需要定义大小)
    vector<int> element, next;  // 对应链表的element和next
    int index;  // 链表的index
};

// 哈希结构——开放地址法
class OpenHash {
public:
    int find(int x) {
        int k = (x % HashN + HashN) % HashN;
        // 寻找合适位置
        while (element[k] != null && element[k] != x) {
            k++;
            if (k == HashN) k = 0;
        }
        return k;
    }

private:
    vector<int> element;    // 元素应该初始化为 0x3f3f3f3f
    int null = 0x3f3f3f3f;  // 通常想要用memset把数字设为最大值时：memset(arr, 0x3f, sizeof(arr))
};

// 字符串哈希
// href: https://www.acwing.com/blog/content/404/

// _________________________________HELP　FUNC_________________________________
void Func_quick_sort(vector<int> &nums, int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = nums[l + r >> 1];
    while (i < j) {
        do i++; while (nums[l] < x);
        do j--; while (nums[r] > x);
        if (i < j) swap(nums[i], nums[j]);
    }
    Func_quick_sort(nums, l, j);
    Func_quick_sort(nums, j + 1, r);
}

void Func_merge_sort(vector<int> &nums, int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    Func_merge_sort(nums, l, mid);
    Func_merge_sort(nums, mid + 1, r);
    vector<int> tmp(nums.size());
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
}

void Func_heap_down(vector<int> &nums, int u) {
    int t = u;
    // 分别和左右孩子进行比较
    if (u * 2 <= nums.size() && nums[u * 2] < nums[t]) t = u * 2;
    if (u * 2 + 1 <= nums.size() && nums[u * 2 + 1] < nums[t]) t = u * 2 + 1;
    if (u != t) {
        swap(nums[u], nums[t]);
        Func_heap_down(nums, t);
    }
}

void Func_heap_up(vector<int> &nums, int u) {
    // 与父节点比较，大的话换上去
    while (u / 2 > 0 && nums[u / 2] > nums[u]) {
        swap(nums[u / 2], nums[u]);
        u /= 2;
    }
}

void AcWingdfsPermutation(vector<string> &res, vector<bool> &used, string &path, string &s) {
    if (path.size() == s.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < s.size(); i++) {
        if (!used[i]) {
            if (i >= 0 && s[i] != s[i - 1] && !used[i - 1]) continue;
            path.push_back(s[i]);
            used[i] = true;
            AcWingdfsPermutation(res, used, path, s);
            path.pop_back();
            used[i] = false;
        }
    }
}

// N皇后问题检查当前状态是否符合要求——可作为最后结果判断和剪枝
// board表示当前的棋盘，row/col表示dfs到的行、列
bool AcWingisValid(vector<string> &board, int row, int col) {
    // 只需要检查row行之前的内容
    int n = board.size();
    // 检查同列
    for (int i = 0; i < row; i++) {
        if (board[row][col] == 'Q') return false;
    }
    // 检查右上
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    // 检查左上
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }

    return true;
}

void dfsSolveNQueens(vector<vector<string>> &res, vector<string> &path, int row) {
    if (row == path.size()) {
        res.push_back(path);
        return;
    }
    for (int col = 0; col < path[row].size(); col++) {
        if (!AcWingisValid(path, row, col)) continue;   // 剪枝
        path[row][col] = 'Q';   // 在col列放一个Q，所以上一步验证Valid的时候col列不能有Q
        dfsSolveNQueens(res, path, row + 1);
        path[row][col] = '.';
    }
}

// ________________________________CLASS　FUNC________________________________
void TemplateAlgorithm::quickSort(vector<int> &nums) {
    Func_quick_sort(nums, 0, nums.size() - 1);
}

void TemplateAlgorithm::mergeSort(vector<int> &nums) {
    Func_merge_sort(nums, 0, nums.size() - 1);
}

vector<int> TemplateAlgorithm::singleStack(vector<int> &nums) {
    vector<int> res;
    vector<int> stk(N);     // 用于模拟栈
    int top = 0;
    for (int i = 0; i < nums.size(); i++) {
        while (top && stk[top] >= nums[i]) --top;   // 说明栈顶这个元素不会再用到
        if (top) res.push_back(stk[top]);
        else res.push_back(-1);
        stk[++top] = nums[i];   // 入栈
    }
    return res;
}

//vector<int> TemplateAlgorithm::maxSlidingWindow(vector<int> &nums) {
//    if (k <= 0 || nums.empty() || k > nums.size()) return {};
//    vector<int> res;
//    deque<int> findMax;  // 存放索引
//    for (int i = 0; i < nums.size(); i++) {
//        if (i >= k && !findMax.empty()) res.push_back(nums[findMax.front()]);
//        while (!findMax.empty() && nums[i] >= nums[findMax.back()]) findMax.pop_back();
//        if (!findMax.empty() && i - findMax.front() >= k) findMax.pop_front();
//        findMax.push_back(i);
//    }
//    res.push_back(nums[findMax.front()]);
//    return res;
//}

int TemplateAlgorithm::lengthOfLongestSubstring(string s) {
    int res = 0;
    vector<int> hash(200, 0);
    for (int i = 0, j = 0; i < s.length(); i++) {
        hash[s[i]]++;
        while (hash[s[i]] > 1) {
            hash[s[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    return res;
}

// 返回整数中最低位的1
int lowbit(int x) {
    // 同理，两种写法均可
    // return x & (~x + 1);
    return x & -x;
}

int TemplateAlgorithm::numOfOne(int x) {
    int res = 0;
    while (x) {
        x -= lowbit(x);
        res++;
    }
    return res;
}

vector<vector<int>> TemplateAlgorithm::merge(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) { return a[0] < b[0]; });
    vector<vector<int>> res;
    int st = -2e9, ed = -2e9;
    for (auto &seg:intervals) {
        if (seg[0] > ed) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg[0], ed = seg[1];   // 更新当前维护的区间
        } else ed = max(ed, seg[1]);
    }
    if (st != -2e9) res.push_back({st, ed});
    return res;
}

void TemplateAlgorithm::heapSort(vector<int> &nums) {
    for (int i = nums.size() / 2; i > 0; i--) Func_heap_down(nums, i);
}

vector<string> TemplateAlgorithm::permutation(string s) {
    if (s.empty()) return {};
    vector<string> res;
    string tmp = "";
    vector<bool> used(s.size(), false);
    AcWingdfsPermutation(res, used, tmp, s);
    return res;
}

vector<vector<string>> TemplateAlgorithm::solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));   // 初始状态棋盘都为 "."
    dfsSolveNQueens(res, board, 0);     // 从第0行开始
    return res;
}

vector<int> TemplateAlgorithm::topoSort() {
    queue<int> que;
    vector<int> edges[N];
    for (int i = 0; i < N; i++) {   // N:节点的总数
//        if (in[i] == 0) que.push(i);    //将入度为0的点入队列
    }
    vector<int> res;     // 拓扑排序的结果
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        res.push_back(p);
        for (int i = 0; i < edges[p].size(); i++) {
            int y = edges[p][i];
//            in[y]--;
//            if (in[y] == 0) que.push(y);
        }
    }
    return res;
}

// 并查集：返回x的根节点 + 路径压缩
int find(int x) {
    if (tree[x] != x) tree[x] = find(tree[x]);
    return tree[x];
}
